package sort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-27 19:53
 **/
public class CountingSort {

    //优化版
    public static void sort(int[] arr) {
        int n = arr.length;
        if (n <= 1) {
            return;
        }

        //寻找最值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < n; ++i) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        //开辟内存空间,存储次数
        int[] counts = new int[max - min + 1];
        //统计每个整数出现的次数, arr数组中元素对应在counts数组中的索引是arr[i] - min;
        for (int i = 0; i < n; ++i) {
            ++counts[arr[i] - min];
        }

        //counts数组不再保存次数,将其改为前缀和
        for (int i = 1; i < counts.length; ++i) {
            counts[i] += counts[i - 1];
        }

        //使用新数组暂存所有的元素
        int[] newArray = new int[n];
        int i = n - 1;
        //从后往前遍历元素,将它放到有序数组中的合适位置,为了保证稳定性
        while (i >= 0) {
            //--counts[arr[i] - min]: 找到arr[i]的新位置
            newArray[--counts[arr[i] - min]] = arr[i];
            --i;
        }

        //将有序数组赋值回原数组
        while (++i < n) {
            arr[i] = newArray[i];
        }

    }

    //不稳定,无法处理包含负数的数组
    /*public static void sort(int[] arr) {
        //找出最大值
        int max = arr[0];
        //数组长度
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        //开辟内存空间,存储每个整数出现的次数
        int[] counts = new int[1 + max];
        //统计每个整数出现的次数
        for (int i = 0; i < n; ++i) {
            ++counts[arr[i]];
        }

        //根据整数出现的次数,对整数进行排序
        int index = 0;
        for (int i = 0; i < counts.length; ++i) {
            while (counts[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }*/

    public static void main(String[] args) {
        int[] arr = new int[]{7,1,2,3,4,5,6,6,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
